package jzoffer;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Author:   dengxin
 * Date:     2020/6/12 3:55 下午
 * 求二叉树深度
 * 方法1:递归
 * 方法2:层次遍历
 */
@SuppressWarnings("all")
public class jz38 {

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        node1.left = new TreeNode(2);
        node1.left.left = new TreeNode(3);
        node1.right = new TreeNode(4);
        treeDepth1(node1);
        System.out.println(treeDepth1(node1));
        System.out.println(treeDepth2(node1));
    }

    //递归法
    private static int treeDepth1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = treeDepth1(root.left);
        int rightDepth = treeDepth1(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }

    //层次遍历
    private static int treeDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int depth=0, count=0, nextCount=1;
        while (queue.size() != 0) {
            TreeNode top = queue.poll();
            count++;
            if (top.left != null) {
                queue.add(top.left);
            }
            if (top.right != null) {
                queue.add(top.right);
            }
            if (count == nextCount) {
                nextCount = queue.size();
                count = 0;
                depth++;
            }
        }
        return depth;
    }

    static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }

    }
}
